package fun.coding.leetcode;

public class WordSearch {

	public static void main(String[] args) {
		char[][] board = {  {'A', 'B', 'C', 'E'}, 
							{'S', 'F', 'C', 'S'}, 
							{'A', 'D', 'E', 'E'},};
		
		WordSearch ws = new WordSearch();
		System.out.println(ws.exist(board, "ABCCED"));
		
		System.out.println(ws.exist(board, "ABCB"));
	}
	
	public boolean exist(char[][] board, String word) {
		if (board == null || word == null) return false;
		
		if (board.length == 0 || word.isEmpty()) return false;
		
		boolean[][] visited = new boolean[board.length][board[0].length];
		
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				boolean isExist = helper(board, i, j, word, 0, visited);
				if (isExist) {
					return true;
				}
			}
		}
		return false;
	}

	public boolean helper(char[][] board, int row, int col, String word, int index, boolean[][] visited) {
		// Final condition, as long as there is no char left in the word, we are done.
		if (index == word.length()) {
			return true;
		}
		
		if (row >= board.length || row < 0 || 
				col >= board[0].length || col < 0) {
			return false;
		}
		
		if (board[row][col] != word.charAt(index) || visited[row][col]) {
			return false;
		}
		
		visited[row][col] = true;
		
		boolean isExist = helper(board, row-1, col, word, index + 1, visited) ||
						   helper(board, row, col + 1, word, index + 1, visited) ||
						   helper(board, row+1, col, word, index + 1, visited) ||
						   helper(board, row, col - 1, word, index + 1, visited);
				
		visited[row][col] = false;
		return isExist;
	}
}
